package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/partition-list/
 * 分割链表
 * 此题是Code16_listPartition的阉割版
 */
public class Code26_listPartition2 {

    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1,1);
        int target = 0;
        ListNode ans = partition(head, target);
        ListNodeUtils.print(ans);
    }
    public static ListNode partition(ListNode head, int target) {
        if (head == null|| head.next==null) {
            return head;
        }
        ListNode cur = head, next = null;
        ListNode sH = null, sT = null, mH = null, mT = null;
        while (cur != null) {
            next = cur.next;
            cur.next = null;
            if (cur.val < target) {
                if (sH == null) {
                    sH = cur;
                    sT = cur;
                } else {
                    sT.next = cur;
                    sT = cur;
                }
            } else {
                if (mH == null) {
                    mH = cur;
                    mT = cur;
                } else {
                    mT.next = cur;
                    mT = cur;
                }
            }
            cur = next;
        }
        if (sT != null) {
            sT.next = mH;
        }
        return sH == null ? (mH == null ? mH : head) : sH;
    }
}
